<!doctype html>
<html lang="zh_cn" itemscope itemtype="http://schema.org/Person">
<head>
            <meta charset="utf-8">
        <!-- Site Meta Data -->
        <title>KMP算法前传之朴素匹配算法回溯位置计算详解Java版</title>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="description" content="技术博客,涉及Java/PHP/Python/Javascript等,聊聊程序,聊聊生活,聊聊事实,聊聊育儿">
        <meta name="keywords" content="编码经验,技术分享,生活积累,实事评说">
        <meta name="author" content="布丁缘">

        <link rel="shortcut icon" href="">

        <link href='https://fonts.googleapis.com/css?family=Open+Sans:400,600,700' rel='stylesheet' type='text/css'>
        <!-- Style Meta Data -->
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/style.css" type="text/css"/>
        <link rel="stylesheet" href="https://www.ddkiss.com/theme/css/pygments.css" type="text/css"/>

        <!-- Feed Meta Data -->
            <link href="https://www.ddkiss.com/feeds/all.atom.xml" type="application/atom+xml" rel="alternate"
                  title="一个程序员的简单生活 ATOM Feed"/>


    <meta name="keywords" content="">
    <link rel="stylesheet" href="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/default.css">
</head>

<body>
<!-- Sidebar -->
<aside>
    <center><h1><a href="/" style="color:#fff"><img id="avatar" src="/images/avatar.jpg"></a></h1></center>
        <p>一个程序员的简单生活</p>
    <br>
    <nav class="nav">
        <ul class="list-bare">
                <li><a class="nav__link" href="https://www.ddkiss.com/category/chang-yong-ji-qiao.html">常用技巧</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/kai-fa-huan-jing.html">开发环境</a></li>
                <li><a class="nav__link" href="https://www.ddkiss.com/category/sheng-huo-dian-di.html">生活点滴</a></li>

                <li><a class="nav__link" href="/pages/books.html">书单</a></li>
                <li><a class="nav__link" href="/pages/movies.html">影单</a></li>
                <li><a class="nav__link" href="/pages/downloads.html">下载</a></li>
                <li><a class="nav__link" href="/pages/about.html">关于我</a></li>


        </ul>
    </nav>


    <form>
      <input type="text"  id="bdcsMain"/>
    </form>

</aside>

<!-- Content -->
<article>
  <main>
    <nav>
      <a href="/">首页</a>
      <a href="/archives.html">归档</a>
      <a href="/categories.html">分类</a>
      <a href="/tags.html">标签</a>
      <a href="/pages/about.html">关于我</a>
    </nav>
  </main>
    <section id="content">
        <article>
            <h2 class="post_title post_detail"><a href="https://www.ddkiss.com/archives/60.html" rel="bookmark"
                                                  title="Permalink to KMP算法前传之朴素匹配算法回溯位置计算详解Java版">KMP算法前传之朴素匹配算法回溯位置计算详解Java版</a></h2>

            <div class="post_list">
                <span>作者：</span><a href="https://www.ddkiss.com/author/bu-ding-yuan.html">布丁缘</a>
                <span class="post_category">分类：<a href="https://www.ddkiss.com/category/kai-fa-huan-jing.html" rel="bookmark"
                                               title="Permalink to 开发环境">开发环境</a></span>
                <span class="post_date">  时间：2017-10-12 14:39:00</span>

            </div>
            <div class="entry-content blog-post">
                <p>KMP算法是由朴素匹配算法优化而来的。最近，重新了解朴素匹配算法，发现网上的文章对于i的回溯没有讲得很清楚，比如<a href="http://blog.csdn.net/v_july_v/article/details/7041827">从头到尾彻底理解KMP</a>中提到的<code>如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0</code>，当时看到的时候没想明白为啥？另外，有的书都是以<code>i=1,j=1</code>开始，有的书是以<code>i=0,j=0</code>开始，这两种方式是有区别的。特别是回溯<code>i</code>时。</p>
<p>朴素匹配算法，网上有很多介绍。为了方便，下面约定如下：原串为<code>s</code>,位置为<code>i</code>，待匹配串为<code>p</code>，位置为<code>j</code>。如果<code>s[i]==p[j]</code>则继续比较，否则，<code>j</code>回到初始位置，而<code>i</code>则回到<code>最近一次移动前位置的下一位</code>。所以，难点就在于每次如何计算<code>i</code>的位置。</p>
<p>先按<code>i=0,j=0</code>实现，参考下面的图
<img alt="QQ截图20171012140456_1_2_3.jpg" src="https://www.ddkiss.com/usr/uploads/2017/10/205750792.jpg"></p>
<p>图中，坐标原点是０,也就是循环从０开始。其他文章或者书中都是用图中红色方框里的方式表示匹配过程，好处是比较直白，坏处是没法算清楚回溯的位置了。我推荐用图中上半部分的方式理解，匹配的过程，实际上是虚线以某个角度(0&lt;x&lt;90)向右平移的过程。并且每次开始匹配，都是从<code>p</code>的位置０开始。<strong>注意:图中<code>i</code>和<code>j</code>不一定只相差1，可以是任意值，取决于<code>p</code>第一个字符匹配时<code>i</code>的位置。</strong>用<code>java</code>实现是</p>
<div class="highlight"><pre><span></span>    public int naiveMatch(String source, String pattern) {
        //回溯i
        int i = 0;
        int j = 0;

        char[] sArr = source.toCharArray();
        char[] pArr = pattern.toCharArray();

        int sLen = sArr.length;
        int pLen = pArr.length;

        while (i &lt; sLen &amp;&amp; j &lt; pLen) {
            if (sArr[i] == pArr[j]) {
                i++;
                j++;
            } else {
                i = (i - j) + 1; // 此时j 表示p走过的长度
                j = 0;
            }
        }

        if (j &gt;= pLen) {
            return i - j;//或　i - pLen
        } else {
            return -1;
        }
    }
</pre></div>


<p>如果是从<code>i=1;j=1</code>开始呢？那计算回溯位置的时候就需要把开头的１加上。java代码如下：</p>
<div class="highlight"><pre><span></span>    public int naiveMatch2(String source, String pattern) {
        int i = 1;
        int j = 1;

        char[] sArr = source.toCharArray();
        char[] pArr = pattern.toCharArray();

        int sLen = sArr.length;
        int pLen = pArr.length;

        char[] nsArr = new char[sLen + 1];
        char[] npArr = new char[pLen + 1];

        System.arraycopy(sArr, 0, nsArr, 1, sArr.length);
        System.arraycopy(pArr, 0, npArr, 1, pArr.length);

        while (i &lt;= sLen &amp;&amp; j &lt;= pLen) {
            if (nsArr[i] == npArr[j]) {
                i++;
                j++;
            } else {
                i = (i - j + 1) + 1; //(i-j)是距离，(i-j+1)是原索引位置，(i-j+1+1)是新的索引位置
                j = 1;
            }
        }

        if (j &gt; pLen) {
            return i - (j - 1); // 此时 (j-1) == pLen
        } else {
            return -1;
        }

    }
</pre></div>


<p>注意：回溯的时候<code>i</code>是索引，必须加上初始变量<code>1</code></p>
<p><strong>纯Java</strong>的写法可以优化为：</p>
<div class="highlight"><pre><span></span>public int naiveMatchJava(String source, String pattern) {
        int i = 0, j = 0;
        while (i &lt; source.length() &amp;&amp; j &lt; pattern.length()) {
            if (source.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                i = (i - j) + 1;
                j = 0;
            }
        }

        if (j &gt;= pattern.length()) {
            return i - pattern.length();
        } else {
            return -1;
        }
    }
</pre></div>
            </div>
            <div class="post_list">
              <div><span>Tags : </span>
              </div>
            </div>
        </article>
        <div id="container"></div>
        <script type="text/javascript" src="//dn-coding-net-public-file.qbox.me/Coding-Comments/v0.1.0/gitment.min.js"></script>
        <script>
            var gitment = new Gitment({
              owner: 'whusl',
              repo: 'BlogComments',
              oauth: {
                client_id: '621866266817529fba46681653017809',
                client_secret: '14188411740b12ae52159cee9b586bf85cd54125',
              },
            })
            document.getElementById('container').appendChild(gitment.render())
          </script>
    </section>
</article>

<!-- Footer -->
    <footer>
        <p> &copy;2017-2020&nbsp;<a href="http://www.miitbeian.gov.cn/" target="_blank">鄂ICP备17020200号</a>
          Blog powered by <a href="http://getpelican.com/">Pelican</a>
        </p>
    </footer>

    <!-- Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?88c55edaf311dbacac56a16316b04c8b";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>

<script type="text/javascript">(function(){document.write(unescape('%3Cdiv id="bdcs"%3E%3C/div%3E'));var bdcs = document.createElement('script');bdcs.type = 'text/javascript';bdcs.async = true;bdcs.src = 'http://znsv.baidu.com/customer_search/api/js?sid=14490611060029767912' + '&plate_url=' + encodeURIComponent(window.location.href) + '&t=' + Math.ceil(new Date()/3600000);var s = document.getElementsByTagName('script')[0];s.parentNode.insertBefore(bdcs, s);})();</script>

</body>
</html>